1. Field of the Invention
This invention relates in general to spread spectrum receivers and in particular to GPS navigation systems such as those used in terrestrial navigation for cars, trucks and other land vehicles.
2. Description of the Prior Art
Car navigation is conventionally performed using highway and street maps aided, to some degree, by distance measurements from external sensors such as odometers. Improvements over the last 10 years in Global Positioning System, or GPS, satellite navigation receivers has spawned several GPS car navigation systems.
Conventional GPS car navigation systems use the last known position of the vehicle, and the destination data, to compute a route data base, including route and turning data derived from a pre-existing map data base. GPS receivers are conventionally operated with a minimum of 3 or 4 satellites distributed across the visible sky in order to determine, or at least estimate, the four necessary unknowns including xuser, yuser, and zuser which provide three orthogonal coordinates to locate the user as well as tuser which provides the required satellite time. Techniques such as time or clock hold and altitude hold, in which the unknown time or altitude is assumed to remain predictable from a previously determined value, e.g. zest and/or test, have permitted operation of GPS receivers with less than 4 satellites in view. In particular, terrestrial GPS receivers have been operated with as few as 2 satellites to provide a 2 dimensional position solution using both clock and altitude hold.
Because continuous reception from 4 GPS satellites is often difficult to maintain in a car navigation environment, and known clock and altitude hold techniques can only permit operation with at least 2 satellites, known conventional car navigation systems have typically augmented the GPS position information with information from external sensors to provide dead reckoning information. The dead reckoning information is often provided by an inertial navigation system such as a gyroscope.
Augmenting GPS data with inertial navigation data has permitted the use of GPS car navigation even when less than 4 satellites are visible, such as in tunnels and in urban situations between tall buildings. However, the resultant increased complexity and costs for such combined systems have limited their acceptance.
Conventional GPS receivers use separate tracking channels for each satellite being tracked. Each tracking channel may be configured from separate hardware components, or by time division multiplexing of the hardware of a single tracking channel, for use with a plurality of satellites. In each tracking channel, the received signals are separately Doppler shifted to compensate for the relative motion of each satellite and then correlated with a locally generated, satellite specific code.
During a mode conventionally called satellite signal acquisition, delayed versions of the locally generated code for the satellite being acquired are correlated with the Doppler rotated received signals to synchronize the locally generated code with the code, as received for that satellite, by determining which delay most accurately correlates with the code being received. Once synchronization has been achieved for a particular satellite, that satellite channel progresses to a tracking mode in which the Doppler rotated, received signal is continuously correlated with the locally generated code for that satellite to determine position information including pseudorange information. During tracking, conventional receivers also correlate the Doppler shifted received signal with one or more versions of the locally generated code at different relative delays, such as one half C/A code chip width early and late relative to the synchronized or prompt version of the code. These early and late correlations are used to accurately maintain the synchronization of prompt correlation.
When, after tracking has begun for a particular satellite, the satellite signal has been lost so that the required timing of the locally generated code for synchronization is no longer accurately known, conventional receivers reenter the acquisition mode, or a limited version of this mode, to reacquire the satellite signals by multiple correlations to resynchronize the locally generated code with the code as received. Once the locally generated code has been resynchronized with the signals as received, position information data is again derived from the signals from that satellite.
GPS systems, as well as many other radio frequency (RF) communication systems utilizing frequencies high enough to be considered line of sight systems in which there must be a substantially direct line of sight between the transmitter(s) and receivers(s) for optimum operation, often suffer from multipath effects in which the receiver(s) must process signals received over a multiplicity of different paths. A common example is a simple broadcast TV system in which a TV receiver with an antenna receives multiple copies of the signal being transmitted.
The multiplicity of signals being received results from additional, typically unwanted, signals paths including one or more reflections. When the signal path from the transmitter to receiver includes a reflection, this signal path must by definition be longer than the direct path. Multipath signals present a problem in systems, such as GPS systems, in which the time of arrival of the signal is to be measured or used because the time of arrival of the multipath signals depends on the length of the path(s) taken.
The straightforward processing of all signals, including multipath or reflected signals, often degrades the processing performed by the receiver. In the simple broadcast TV transmission system described above, the processing of unmodified multipath signals by the receiver results in the commonly experienced degradation called xe2x80x9cghostingxe2x80x9d in which multiple signals are displayed offset in the TV image. The multiplicity of displayed offset video signals results from the difference in path lengths of the various multipath signals received.
The direct path is the shortest and therefore requires the least travel time from transmitter to receiver while the various unwanted multipath signals have various greater lengths, and therefore various longer travel times, than the direct path signals. Signals are processed in part in a TV receiver in accordance with their time of arrival and therefore the resultant video display may include a plurality of images slightly displaced in space on the TV monitor in accordance with their different path lengths.
Many conventional partial solutions to the problems of multipath reception exist. In the TV broadcast example, a highly direction antenna is often used for the receiver to reduce the number of multipath signals processed by the receiver. In addition, various discrimination techniques have been developed which use the knowledge that the amplitude of the direct path signal is typically substantially greater than that of the unwanted multipath signals because signal amplitude is degraded by the square of the path length.
In other types of systems, such as the GPS systems using PRN encoded spread spectrum signals, certain conventional techniques are difficult or impossible to use. For example, GPS transmitters are positioned on satellites with complex orbital paths so that the position of the multiple transmitters are constantly changing. This makes a highly directional antenna system almost completely unusable. Similarly, digital receivers, including those used in a GPS receiver, often do not rely solely on the amplitudes of the signals received, but rather rely on other signal characteristics, such as time of arrival.
Multipath processing techniques currently used for complex receivers, such as GPS receivers, are often quite complex and subject to inaccuracies. An example of one such conventional technique is described in U.S. Pat. No. 5,414,729 issued on May 9, 1995 to Patrick Fenton and assigned as issued to NovAtel Communications Ltd., Canada. In this technique, an autocorrelation function of a partially processed received signal, including multipath components, is compared to an estimated autocorrelation function of an estimated direct path signal to attempt to discern direct path signals from multipath signals for further processing. This technique of comparing processed and estimated correlation power, is complex and may be subject to error in that the partially processed signals relied on are themselves subject to degradation from many effects in addition to multipath effects including receiver limitations, which may reduce the accuracy or effectiveness of the multipath processing techniques.
For example, in tracking a GPS C/A signal to determine position information from GPS satellite transmitters, it is typically important to derive an accurate estimate of the time of arrival, known as code phase, of the PRN modulation of the direct path component of the C/A signals received from each of the various GPS satellites. It is also important to derive an accurate estimate of the phase of the underlying carrier signals transmitted from the satellites on which the modulation is applied, known as the carrier phase. However, as apparently shown for example in FIGS. 6, 7 and 8 of the above referenced Fenton patent, the delayed multipath components degrade the tracking of the code and carrier phase estimates by distorting the correlation functions used is such tracking.
What is needed is an improved spread spectrum receiver, such as one for use with GPS navigation systems, which avoids the limitations of conventional designs and provides improved results in a wide range of reception conditions, including multipath interference.
In one aspect, the present invention provides an improved terrestrial navigation system using a GPS receiver which can continue to navigate with continuous GPS data from less than the 3 or 4 GPS satellites commonly required. The GPS data is augmented with data from another source. The source of the augmentation data may include data from external sensors, data bases including map data bases, and/or knowledge of the physical environment within which the vehicle is to be navigated. The use of such augmentation data permits GPS satellite navigation solutions for stand-alone GPS systems as well as for GPS systems integrated with external sensors and/or map databases with less than 3 or 4 continuously visible GPS satellites.
In other aspect, the present invention provides a GPS system which uses a digital ASIC and RF chipset and a relatively wide IF band. A simple, 2-pole LC IF filter is associated with the RF chip while a decimator or digital filter associated with the digital chip to run the system at a reduced clock rate. The simple 2-pole filter is used in lieu of the more complex and expensive 5 or 6 pole filter that would otherwise, be used in a conventional receiver system of this type.
In another aspect, the present invention provides a GPS receiver in which map data used to determine routing is also used as a source of data augmentation for a single satellite solution by providing direction of travel information.
In still another aspect, the present invention provides a method of augmenting GPS data using information from the physical environment. For example, vehicles are usually constrained to tracks no wider than the width of the roadwayxe2x80x94and often to tracks only half the width of the roadwayxe2x80x94and trains are constrained to the width of their tracks. This cross track constraint data may be used to provide augmentation data and allow the vehicle to continue to navigate with only a single satellite in view. The cross track constraint data permits the computation of along track data useful for calculating total distance traveled to provide a GPS based odometer measurement.
The present invention permits the computation of distance along track for use as an odometer reading while tracking only one satellite. Cross track hold provides along-track data directly which, in the case of a vehicle, directly provides distance traveled information useful in lieu of a conventional odometer reading.
In addition to clock and altitude hold, the present invention uses a technique which may be called cross-track hold in which the single satellite in view is used for determining the progress of a vehicle such as a car along its predicted track, such as a roadway. The data conventionally required from a second satellite is orthogonal to the track and therefor represents the appropriate width of the roadway. This value may be assumed and or constrained to a sufficiently small value to permit an estimate of the value, e.g. yest to provide a mode described herein as cross-track hold while obtaining useful GPS navigation from a single satellite in view.
In other words, in accordance with the present invention, single satellite navigation may be achieved by using the data from the single satellite for on-track navigation information while holding or estimating the time, altitude and/or cross-track navigation data.
The required augmentation data may additionally, or alternatively, be derived from other sources in the physical environment, such as turns made by the vehicle during on-track travel. In accordance with another aspect of the present invention, the vehicle may detect turns made during travel and update the current position of the vehicle at the turn in accordance with the timing of the turn. Turn detection may be accomplished by monitoring changes in the vehicle vector velocity derived from changes in the GPS derived position information or by monitoring changes in the compass heading or by any other convenient means.
In another aspect, the present invention provides a GPS system for navigating a vehicle along a track, including means for tracking at least one GPS satellite to provide on-track information related to progress of the vehicle along a selected track, means for providing an estimate of cross track information related to motion of the vehicle perpendicular to the track, and means for providing vehicle navigation data, such as vehicle position or vehicle velocity, from the on-track information and the cross-track estimate.
In still another aspect, the present invention provides a method of deriving position information from a single GPS satellite by tracking at least one GPS satellite to provide on-track information related to progress of the vehicle along a selected track, providing an estimate of cross track information related to motion of the vehicle perpendicular to the track, and determining the position of the vehicle from the on-track and the cross-track estimates.
In still another aspect, the present invention provides a method of updating GPS position information for a vehicle navigating on roadways by deriving an indication that the vehicle has made a turn at a particular point along a predetermined track, comparing the turn indication with stored navigation data to select data related to one or more predicted turns at or near the particular point, comparing the turn indication with the predicted turn data to verify that the indicated turn corresponds to the predicted turn, and updating GPS position information to indicate that the vehicle was at the predicted turn location at a time corresponding to the turn indication.
In still another aspect, the present invention provides a GPS system for navigating a vehicle, the system including means for tracking at least one GPS satellite to provide on-track information related to the direction of travel of the vehicle along a selected track, and means for deriving vehicle navigation data from changes in the direction of travel of the vehicle along the selected track.
In a still further aspect, the present invention takes advantage of the typical improvement in satellite visibility possible in urban roadway intersections by providing a fast satellite reacquisition scheme which permits data from otherwise obscured satellites to aid in the navigation solution even though visible only for a short time, for example, as the vehicle crosses an intersection in an urban environment in which tall buildings obscure the satellites from view except in the intersection.
In a further aspect, the present invention provides a spread spectrum receiver having means for providing a plurality of versions of a locally generated signal related to a spread spectrum signal to be received, means for combining at least two of the versions of the locally generated signal with the spread spectrum signal to produce a product signal related to each of the at least two versions, means for evaluating the at least two product signals to adjust a parameter of the third version of the local signal, means for combining the adjusted third version of the local signal with the spread spectrum signal to produce a data signal, means for determining a predicted value of the parameter when the spread spectrum signal becomes unavailable, means for combining an additional plurality of versions of the locally generated signal related to the predicted value with received signals to produce additional product signals related to each of the additional plurality of versions of the locally generated signal, means for evaluating the additional product signals to produce a reacquired data signal.
In another aspect, the present invention provides a method of operating a receiver for coded GPS signals from satellites by correlating early, prompt and late versions of a locally generated model of the code with signals received from GPS satellites to adjust a delay of the prompt version to track a selected satellite, maintaining a predicted value of the delay when the selected satellite is unavailable, correlating a plurality of different early versions of the locally generated code with signals received from satellites to produce correlation products, correlating a plurality of different late versions of the locally generated code with signals received from satellites to produce correlation products, and reacquiring the previous unavailable selected satellite by selecting the version producing the largest correlation product above a predetermined threshold as a new prompt version of the code to track the satellite.
In a still further aspect, the present invention provides a spread spectrum receiver for a spectrum spreading code having a fixed number of bits repeated during a fixed length time period from a plurality of transmitters having a first time slicing level for slicing the time period of the transmitted code into a number of time segments evenly divisible into the twice the number of samples, a second multiplexing level for dividing each time segment into a number of channels, each of the channels being used for tracking one of the transmitters, and a third level dividing each of the channels in one of the segments into a number of code phase delay tests.
In another aspect, the present invention provides a receiver for processing signals from a plurality of sources, each modulated by a different spectrum spreading code repeating at a common fixed interval, including a sampler for deriving digitally filtered I and Q samples from a composite of spread spectrum signals received from the plurality of sources, means for segregating samples of the signals being received during each interval into a number of time segments, a time division multiplexer for segregating different versions of the sequential samples into each of a number of channels, each channel representing one of the plurality of sources, a correlator for correlating the version of the sample in each channel with a series of sequentially delayed versions of the spectrum spreading code applied to the signals from the source represented by that channel, and an accumulator associated with each of the series of delays in each of the channels for processing the results of correlations performed during one or more intervals to derive information related to the signals.
In another aspect, the present invention provides a GPS receiver in which the residual code phase tracking, or pseudorange, error due to simultaneous reception of multipath signals is detected, estimated and corrected. In particular, the distortion of the correlation function of the multi- and direct path signal composite as received with the internally generated code is detected by comparison of an aspect of resultant correlation function with a model of the correlation function expected in the absence of multipath distortion. The comparison provides an indication of the sign of the residual error.
It has been determined that the composite of a direct path and one or more multipath signals distorts the correlation function. If, as in most common cases, the multipath signal(s) are weaker than the direct path signals, the interference between such signals as received results in a predictable distortion of the correlation function. If the carrier phase(s) of the multipath signal(s) are shifted from between about 0xc2x0 to 90xc2x0 from the carrier phase of the direct path signal, the signals tend to reinforce each other resulting in a widening of the correlation function. Similarly, if the carrier phase(s) of the multipath signal(s) are shifted from between 90xc2x0 to about 180xc2x0 from the carrier phase of the direct path signal, the signals tend to cancel each other resulting in a narrowing of the correlation function.
The correlation products are used in a code tracking loop to track and determine code phase. The most common scheme is to track points of equal magnitude (or power) separated by one C/A code chip width and estimate the time of arrival of the direct path signal as the mid-point between these points of equal magnitude. The points of equal magnitude on either side of the direct path arrival time are known as the early and late correlation time and the estimated arrival time of the direct path is called the punctual correlation time. In the presence of multipath signals, the correlation function has been found to be distorted so that the mid-point between the early and late correlations, that is the prompt correlation, is not an accurate estimation of the arrival time of the direct path signal.
When the correlation function of the composite is distorted to be wider than the correlation function expected for a direct path only signal, the distortion results in a lag error in which the prompt correlation lags the actual direct path signal received. similarly, when the correlation function of the composite is narrower than expected, the distortion results in a lead error in which the prompt correlation leads the time of arrival of the direct path signal.
The prompt correlation therefore leads or lags the actual time of arrival of the direct path signal by an amount designated herein as the residual code tracking error. The magnitude of the error can be approximated by the degree of narrowing or widening of the correlation function. Reduction of this error, or detection and correction of the error, enhances the accuracy of the resultant position determination.
The present invention also provides an improved multipath signal processing technique which directly cancels the effect of multipath signals by processing the composite of direct and multipath signals as received to create a synthesized replica of the signal as received which may then be subtracted from the signals as received to cancel or eliminate the effects of the non-direct path, unwanted multipath signals. As a result of the steps required to create a replica which will actually cancel the signal as received, the actual carrier and code phases are accurately determined without degradation by multipath components. The cancellation may preferably occur after the received signals have been partially processed to reduce complexity of the system and required signal processing and enhance accuracy of further processing.
In another aspect, the present invention provides an improved technique for multipath signal processing in which a tracking loop applied to the signal as received is used to synthesize an accurate replica of the signals as received, including multipath components. The replica is then canceled from the signal being processed to decode the signal as received without multipath degradation. The replica signal is synthesized to approximate, using least squares or similar approximation techniques, the GPS signal as received including distortions caused by multipath. This provides a useful estimate of the multipath signal profile. From this estimate, relatively accurate measurements of code and carrier phase of the direct path GPS signal received are derived.
In still another aspect, the present invention provides a spread spectrum receiver including a multi-bit digital correlator for correlating each sequential segment of a spread spectrum signal with at least one series of differently time delayed code replicas and matrix means responsive to the correlator to derive code source specific information. The multibit correlator may be configured from a set of correlators for simultaneously correlating portions of each sequential segment with portions of a segment of a code replica. The series of differently time delayed code replicas may be sequential or interlaced.
For efficient C/A GPS operation, each segment should include a signal sample having a duration of an integral number of half chip widths proportional to a number selected from 3, 11 and 31 while the number of satellite channels and time delays are proportional to the others of those numbers. The multi-bit correlator operates upon a first sequential segment while the sample register collects a subsequent sequential segment. The matrix means includes m times n data cells for storing data related to the correlation of the spread spectrum signal and the receiver may be selectively operated the receiver to form either n different code specific sets of m different time delayed correlation products or n times m different time delayed correlation products for one code.
The series of time delayed code replicas covers a tracking window of time sufficient to track a prompt time delay from a selected code transmitter as well as additional time delayed code replicas covering a recapture window of time separate from the tracking window. The recapture window is sufficiently large to include a prompt time delay correlation product for each code after predictable periods of code transmitter obscuration during normal operation of the receiver.
Multipath performance is improved by use of tracking means responsive to the matrix means for tracking a prompt delay from a source of the code together with means for monitoring correlation products representing lesser time delays than the prompt delay to detect the inaccurate tracking of a multipath signal from the source of the code. In addition, multipath errors are reduced by analyzing the ratios of correlation products surrounding the prompt correlation to correct for interference using means for causing correlation products of two of the time delayed replicas to be equal together with means for selecting the prompt delay in response to the ratio of the amplitude of the equal correlation products to a correlation product having a time delay therebetween. The prompt time delay is selected to be less than half way between the time delays of the equal correlation products if the ratio of the amplitudes of the equal correlation products to a correlation product having a time delay half way between the time delays of the equal correlation products is greater than one or more than half way between the time delays of the equal correlation products if the ratio of the amplitudes of the equal correlation products to a correlation product having a time delay half way between the time delays of the equal correlation products is less than one.
IF bandwidth improvement is provided by use of sampling means for forming digitized samples of signals received from code sources at a first rate and digital filtering means for forming the sequential segments from the digitized samples at a second rate substantially slower than the first rate.
Hand held operation is aided by use of means for temporarily interrupting correlation for multiple code periods to reduce receiver energy consumption and means for resuming correlation to continue deriving code source specific information. The correlation may be resumed periodically to provide an apparently continuous display. The periods of interruption are a multiple of the code period and short enough so that unmodeled clock drift is less than the difference in time between the time delays used for the correlation of signals from a code source. Correlation may also be resumed in response to means for modeling clock drift for synchronizing a local clock with a clock associated with a single source of the code or in response to operator interaction.
In a still further aspect, the present invention provides a method of operating a GPS C/A code receiver by forming x multibit digital segment values per C/A code period, each representing a sequential segment of a received composite of satellite signals, correlating each digital segment value with n satellite specific sets of m differently time delayed segments of C/A code modulation to form at least n times m time delay specific correlation values, and determining navigation information from the correlation values, where x, m and n are each prime factors of the number code chips per C/A code period.
Multipath performance is improved by comparing the magnitudes of two equal correlation values to the magnitude of a correlation value therebetween to select a prompt delay more than half way between the time delays represented by the equal correlation values when the magnitude of the equal correlation products is equal to less than half of a peak correlation value therebetween or less than half way between the time delays represented by the equal correlation values when the magnitude of the equal correlation products is equal to more than half of a peak correlation value therebetween.
Battery operation is improved by interrupting the step of correlating for a series of code periods to reduce receiver energy consumption. The interruption period is less than the time required for an internal receiver clock to drift the time delay represented by the series of time delay segments related to one particular satellite. Correlation is resumed periodically to update the display or to update the internal clock or in response to operator intervention in a push-to-fix mode.